CSE 373: Data
Structures and Algorithms
Winter 2000
Assignment 2 Chapter 3
Solutions
assume we'll be given the pointer to the first node of the two
adjacent nodes.
singly
linked list:
void swap(node* head, node* p)
{
if (head->next==NULL)
return;
if ( !p )
return;
node* itr=head;
while (itr->next!=p)
itr=itr->next;
itr->next=p->next;
if (!p->next)
{
delete p;
return;
}
node* temp=p->next->next;
p->next->next=p;
p->next=temp;
}
doubly
linked list:
void swap(node* head, node* p)
{
if (head->next==NULL)
return;
if ( !p)
return;
node* q=p->next;
if (!q)
{
p->prev->next=NULL;
return;
}
p->prev->next=q;
q->prev=p->prev;
p->next=q->next;
q->next->prev=p;
p->prev=q;
q->next=p;
}
// psuedo code only. not in exact syntax of c or c++
//
// assume: both list1 and list2 are sorted in accending order
intersect(list1,list2)
{
p1 = list1.head
p2 = list2.head
list list3
while(p1 && p2)
if (p1->element >
p2->element)
p2 = p2->next
else
if (p1->element < p2->element)
p1 = p1->next
else list3.append(p1->element)
return list3
}
union(list1,list2)
{
p1 = list1.head
p2 = list2.head
list list3
// when both list is not
empty
while(p1 && p2)
if (p1->element ==
p2->element)
p3.append(p1->element)
p1 = p1->next
p2 = p2->next
else
while (p1->element > p2->element)
p3->append(p2->element)
p2 = p2->next
while (p1->element < p2->element)
p3.append(p1->element)
p1 = p1->next
// when one or both lists are
exhausted
while(p1)
list3.append(p1->element)
p1 = p1->next
while(p2)
list3.append(p2->element)
p2 = p2->next
}
a.
advantages:
less work to do when deleting, especially when the
underlying data structure is array-based. Instead of moving all the following
elements forward, which is O(N), we can just mark it as deleted, which is O(1)
in most cases. When inserting a new element, it may be inserted in place of a
deleted element instead of moving all the elements after it forward(
array-based) or allocating new memory for it(list-based).
disadvanges:
It may take more space than the list actually need. and it
may take a long time to delete a node at times.
b.
struct Node
{
ElementType Element;
Position Next;
int deleted;
}
struct
liststruc
{
int num_deleted;
int num_undeleted;
PtrToNode head;
};
typedef struct liststruc *List;
int IsEmpty(List L)
{
return L->num_undeleted==0;
}
int IsLast(Position P, List L)
{
if (P->deleted)
{
cerr << "illegal reference to deleted items";
return 0;
}
if (P->next==NULL)
return 1;
while (P->next)
{
P=P->next;
if (!P->deleted)
return 0;
}
return 1;
}
Position Find(ElementType X, List L)
{
Position P;
P=L->next;
while (P!=NULL&&(P->Element!=X||P->deleted))
P=P->next;
return P;
}
void Delete(ElementType X, List L)
{
Position P, TmpCell;
P=Find(X,L);
if (P!=NULL)
{
P->deleted=1;
L->num_deleted++;
L->num_undeleted--;
if (L->num_deleted >= L->num_undeleted)
Clean(L);
}
}
void Clean(List L)
{
Position itr=L->head, prev=L->head;
while (itr->next!=NULL)
{
prev=itr;
itr=itr->next;
if (itr->deleted)
{
prev->next=itr->next;
free(itr);
itr=prev;
L->num_deleted--;
}
}
}
Position FindPrevious(ElementType X, List L)
{
Position itr1=L->head, itr2=L->head;
while (itr1->next!=NULL)
{
if ( itr1->next->Element==X && !itr1->next->deleted)
return itr1;
if (!itr1->next->deleted)
itr1=itr1->next;
else
{
itr2=itr1->next;
while (itr2->next!=NULL&&itr2->next->deleted)
itr2=itr2->next;
if (!itr2->next)
return itr2;
if (itr2->next->Element==X)
return itr1;
itr1=itr2->next;
}
}
return itr1;
}
void
Insert(ElementType X, List L, Position P)
{
if (P->next!=NULL&&P->next->deleted)
{
P->next->Element=X;
L->undeleted++;
L->deleted--;
}
else
{
Position temp;
temp= new Node;
if (!temp)
FatalError("out of space");
temp->Element=X;
temp->deleted=0;
temp->next=P->next;
P->next=temp;
L->undeleted++;
}
}
Position First (List L)
{
Position P=L->head;
while (p->next!=NULL&&P->next->deleted)
P=P->next;
return P->next;
}
Position Advance(Position P)
{
while (P->next!=NULL&&P->next->deleted)
P=P->next;
return P->next;
}
ElementType Retrieve(Position P)
{
if (P->deleted)
FatalError("reference to deleted node");
return P->Element;
}
void dequeue::push(type x, dequeue d)
{
if d.isempty()
{
node* newnode = new
node
newnode->data = x
newnode->next = null
newnode->prev = null
d.head = newnode
d.tail = newnode
}
else
{
node* newnode = newnode
newnode->data = x
newnode->next =
d.head
newnode->prev = null
d.head->prev =
newnode
d.head = newnode
}
{
type dequeue::pop(dequeue d)
{
if d.isempty()
return
"error"
else
{
node* temp = d.head
d.head =
d.head->next
d.head->prev = null
return temp
}
}
void dequeue::inject(type x, dequeue d)
{
if d.isempty()
{
node* newnode = new
node
newnode->data = x
newnode->prev = null
newnode->next = null
d.head = newnode
d.tail = newnode
}
else
{
node* newnode = newnode
newnode->data = x
newnode->prev =
d.tail
newnode->next = null
d.tail->next =
newnode
d.tail = newnode
}
}
type dequeue::eject(dequeue d)
{
if d.isempty()
return
"error"
else
{
node* temp = d.tail
d.tail =
d.tail->prev
d.tail->next = null
return temp
}
}
to test the direction the stack grows:
void stacktest(BOOL first)
{
int a;
printf("%x ",&a);
if (first)
stacktest(FALSE);
}
call
this function stacktest(TRUE); if the second address is bigger than the first
one, the runtime stack grows toward high memory and vice versa.
to
test how much runtime stack space a procedure takes:
assume the procedure is foo()
//add
the variable first as the exit condition for the recursive call.
BOOL
first=TRUE;
foo()
{
//add this line at the beggining of the function
int a;
printf("%x ",&a);
.....
//add the following code at the end of the function,
if (first)
{
first=FALSE;
foo();
}
}
this
is the most exact measure of how much space a procedure takes.
a runtime stack allocates space for a function like this:
local
variables ^
parameters
|
2nd
call: return
value
|
local
variables |
parameters
|
1st
call: return
value
|
by
calling foo recursively, how much space foo's return value and parameters take
can be measured.